package 递归or回溯;
import java.util.*;
/**
 * 生成数组的所有子集
 * 时间复杂度O(2^n)，空间复杂度O(n)，n为数组长度
 */
public class subsets {
    /**
     * 生成数组的所有子集
     * 
     * @param nums 输入数组
     * @return 所有子集的列表
     */
    public static List<List<Integer>> subsetsM(int[] nums){
        back(nums, 0); // 调用回溯方法生成子集
        return res; // 返回所有子集的列表
    }

    private static List<List<Integer>> res = new ArrayList<>(); // 用于存储所有子集
    private static List<Integer> path = new ArrayList<>(); // 用于存储当前路径

    /**
     * 回溯方法，用于生成子集
     * 
     * @param nums 输入数组
     * @param index 当前索引
     */
    private static void back(int[] nums, int index){
        res.add(new ArrayList<>(path)); // 将当前路径加入结果列表
        if(index == nums.length) // 如果索引等于数组长度，返回
            return;
        for(int i = index; i < nums.length; i++){ // 从当前索引开始遍历数组
            path.add(nums[i]); // 将当前元素加入路径
            back(nums, i + 1); // 递归生成子集
            path.remove(path.size() - 1); // 移除当前元素
        }
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示输入数组
     * 例如：1,2,3 表示一个输入数组
     * 输出格式：所有子集的列表
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[s.length]; // 创建输入数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        System.out.println(subsetsM(nums)); // 输出所有子集
        sc.close(); // 关闭输入流
    }
}
